import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * @author 03010570
 * @date 2020/07/09
 * describe:    LeetCode : 面试题 02.05 、链表求和  https://leetcode-cn.com/problems/sum-lists-lcci/
 */
public class LeetCode_interview_02_05 {

    public static void main(String[] args) {

        ListNode node1 = new ListNode(9);
        node1.next = new ListNode(9);
        node1.next.next = new ListNode(9);

        ListNode node2 = new ListNode(1);
//        node2.next = new ListNode(9);
//        node2.next.next = new ListNode(5);

        ListNode listNode = addTwoNumbers(node1, node2);
        while (listNode != null) {
            System.out.print(listNode.val + "->");
            listNode = listNode.next;
        }
    }

    /**
     * 链表正序 求和
     * 考虑 进位问题，
     * 考虑 长度不一样的问题
     * <p>
     * 使用两个栈 来处理即可，倒序输出
     * 时间复杂度 ： O(M+N)  两个
     * 空间复杂度 ： O(M+N) 两个栈的长度
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        Stack<Integer> res = new Stack<>();
        ListNode node = new ListNode(0);
        ListNode cur = node;
        int carry = 0;
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }

        while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
            int sum = carry;
            sum += stack1.isEmpty() ? 0 : stack1.pop();
            sum += stack2.isEmpty() ? 0 : stack2.pop();

            res.push(sum % 10);

            carry = sum / 10;
        }
        while (!res.isEmpty()) {
            cur.next = new ListNode(res.pop());
            cur = cur.next;
        }
        return node.next;


    }


    /**
     * 代码简洁些
     * 链表为 null ,补 0
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0);
        ListNode cur = node;
        int carry = 0;
        while (l1 != null || l2 != null || carry > 0) {
            int curSum = carry;
            curSum += l1 == null ? 0 : l1.val;
            curSum += l2 == null ? 0 : l2.val;

            cur.next = new ListNode(curSum % 10);
            cur = cur.next;
            carry = curSum / 10;

            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        return node.next;

    }


    /**
     * 思路 ： 用一个 新的带头结点的链表来存储，
     * 需要考虑 位数不一样的问题，
     * 需要考虑 进位的问题
     * <p>
     * 时间复杂度 ： O(M+N)  两个链表的长度
     * 空间辅助度 ： O(N)    长一点的链表的长度
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0);
        ListNode cur = node;
        int carry = 0;
        while (l1 != null && l2 != null) {
            int value = l1.val + l2.val + carry;
            int curValue = value % 10;
            carry = value / 10;
            cur.next = new ListNode(curValue);
            cur = cur.next;

            l1 = l1.next;
            l2 = l2.next;
        }
        ListNode listNode = l1 == null ? l2 : l1;
        while (listNode != null) {
            int value = listNode.val + carry;
            int curValue = value % 10;
            carry = value / 10;
            cur.next = new ListNode(curValue);
            cur = cur.next;
            listNode = listNode.next;
        }
        if (carry != 0) {
            cur.next = new ListNode(carry);
            cur = cur.next;
        }
        return node.next;
    }


}
